home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / KERZNER.ZIP / SELECT.CPP
C/C++ Source or Header  |  1996-03-18  |  4KB  |  160 lines
  1. void SHM_Math::Select(int& N, double* D, double* X, double* C, double K)
  2. { // expects array indices in 1,n range, elements 1 and n are virtual
  3.   // outputs arrays in 0,n-1 range.                               
  4.         double ZMAX = 999999999;
  5.     if (N == 2 || K <= 0) {
  6.         N = 0;
  7.         return;
  8.     }
  9.  
  10.     double* F = new double[N + 1];
  11.     int* H = new int[N + 1];
  12.     int* P = new int[N + 1];
  13.  
  14.     D[1] = ZMAX; X[1] = ZMAX; C[1] = 0;
  15.     D[N] = ZMAX; X[N] = ZMAX; C[N] = 0;
  16.     
  17.     F[1] = 0;
  18.     for (int I = 2; I <= N; ++I) {
  19.         double FMIN = ZMAX; int JMIN = 0;
  20.         double T = 0;
  21.  
  22.         for (int J = I - 1; J >= 1; --J) {
  23.  
  24.             if (J != I - 1) T += K * C[J + 1];
  25.             if (T > FMIN) break;
  26.  
  27.             if (Contradict(D[I], X[I], D[J], X[J])) continue;
  28.  
  29.             double G;
  30.             if (I == 1 || I == N || J == 1)
  31.                 G = T + F[J];
  32.             else
  33.                 G = F[J] + Tension(D[I], X[I], D[J], X[J]) + T;
  34.  
  35.             if (G < FMIN) {
  36.                 FMIN = G;
  37.                 JMIN = J;
  38.             }
  39.         }
  40.  
  41.         F[I] = FMIN;
  42.         H[I] = JMIN;
  43.     }
  44.  
  45.     int MM = 0;
  46.     int M = N;
  47.  
  48.     while (1) {    
  49.         M = H[M];
  50.         if (M == 1) break;
  51.         ++MM;
  52.         P[MM] = M;
  53.     }
  54.     for (M = 1; M <= MM / 2; ++M) {
  55.         int SAVE = P[M];
  56.         P[M] = P[MM - M + 1];
  57.         P[MM - M + 1] = SAVE;
  58.     }
  59.  
  60.     for (M = 1; M <= MM; ++M) {
  61.         D[M] = D[P[M]];
  62.         X[M] = X[P[M]];
  63.         C[M] = C[P[M]];
  64.     }
  65.     N = MM;           
  66.              
  67.     // change to 0,N-1 range
  68.     for (I = 1; I <= N; ++I) {
  69.         D[I - 1] = D[I];  
  70.         X[I - 1] = X[I];
  71.         C[I - 1] = C[I]; 
  72.     }
  73.     delete F;
  74.     delete H;
  75.     delete P;     
  76. }
  77. ---------------------------------------------------------------------
  78. void SHM_Math::Select(int N, OptimizationObject** objects, double K)
  79. { // expects array indices in 1,n range, elements 1 and n are virtual
  80.   // does not renumber arrays, instead sets the 'selected' member
  81.  
  82.     if (N == 2 || K <= 0) {
  83.         return;
  84.     }
  85.  
  86.     for (int i = 1; i <= N; ++i) 
  87.         objects[i]->selected = 0;
  88.  
  89.     double* F = new double[N + 1];
  90.     int* H = new int[N + 1];
  91.     int* P = new int[N + 1];
  92.  
  93.     objects[1]->selected = -1;
  94.     objects[N]->selected = -1;
  95.     
  96.     F[1] = 0;
  97.     for (int I = 2; I <= N; ++I) {
  98.         double FMIN = ZMAX; int JMIN = 0;
  99.         double T = 0;
  100.  
  101.         for (int J = I - 1; J >= 1; --J) {
  102.  
  103.             if (J != I - 1) T += K * objects[J + 1]->grade;
  104.             if (T > FMIN) break;
  105.  
  106.             if (objects[I]->Contradict(*objects[J])) continue;
  107.  
  108.             double G;
  109.             if (I == 1 || I == N || J == 1)
  110.                 G = T + F[J];
  111.             else
  112.                 G = F[J] + objects[I]->Tension(*objects[J]) + T;
  113.  
  114.             if (G < FMIN) {
  115.                 FMIN = G;
  116.                 JMIN = J;
  117.             }
  118.         }
  119.  
  120.         F[I] = FMIN;
  121.         H[I] = JMIN;
  122.     }
  123.  
  124.     int MM = 0;
  125.     int M = N;
  126.  
  127.     while (1) {    
  128.         M = H[M];
  129.         if (M == 1) break;
  130.         ++MM;
  131.         P[MM] = M;
  132.     }
  133.     for (M = 1; M <= MM / 2; ++M) {
  134.         int SAVE = P[M];
  135.         P[M] = P[MM - M + 1];
  136.         P[MM - M + 1] = SAVE;
  137.     }
  138.  
  139.     for (M = 1; M <= MM; ++M) 
  140.         objects[P[M]]->selected = 1;
  141.              
  142.     delete F;
  143.     delete H;
  144.     delete P;     
  145. }
  146.  
  147. And this is the declaration of optimization object class:
  148.  
  149. class OptimizationObject 
  150. {
  151. public:
  152.     int selected;
  153.     double grade;
  154. public:
  155.     OptimizationObject();
  156.     virtual ~OptimizationObject();
  157.     virtual double Tension(OptimizationObject& other) = 0;
  158.     virtual int Contradict(OptimizationObject& other) = 0;
  159. };
  160.